class Solution {//leetcode397——整数替换
public:
    int integerReplacement(int n) {
        int cnt=0;
        long long num=n;
        while(num>1){
            if(num%4==1) num-=1;
            else if(num==3) num-=1;
            else if(num%4==3) num+=1;
            else num/=2;
            cnt++;
        }
        return cnt;
    }
};